本场链接:Codeforces Round #589

闲话

啊这场要做A~D,遗憾的是我BC都差点没搞完,特别是C居然得上$ull$就很蛋疼,到最后都没时间看D了.做题的速度还是有待提高.

A. Distinct Digits

题目大意:给定两个整数$l,r$要求输出在$[l,r]$之间的一个各个数位都不同的数$x$.输出一个即可,无解输出-1.
数据范围:
$1 \leq l,r \leq 10^5$

思路

数据范围较小,直接暴力即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(int x)
{
	int st[10] = {0};
	while(x)
	{
		st[x % 10] ++;
		x /= 10;
	}
	for(int i = 0;i < 10;++i)	
		if(st[i] > 1)
			return 0;
	return 1;
}
int main()
{
	int l,r;scanf("%d%d",&l,&r);
	for(int i = l;i <= r;++i)
	{
		if(check(i))
		{
			printf("%d",i);
			return 0;
		}
	}
	printf("-1");
    return 0;
}

B. Filling the Grid

题目大意:有一个$h*w$的格子纸,给每一行每一列都规定了一个值,表示跟边界相连的连续的几个块必须要被染色.问在满足前提条件下有多少种不同的染色方案,对$10^9+7$取模.

思路

对答案的统计来说,应该是整个格子纸里可以任意选择颜色的格子才有计算的必要,对于一个可以任意染色的格子,他有$2$种选择,因此这个题目就是要求出有多少个格子是可以任意染色的,设为$c$.那么答案就是$2^c$,显然写一个快速幂就可以轻松解决.
考虑怎么计算可以任意染色的格子的数量.显然不可能一个一个的把一行一列丢进去考虑,先假定所有的列都已经加进去了,再一个一个加行,计算新加入的行里有多少个是不受影响的,累加即可.可以顺带判断是否有矛盾的地方.
对于$i$行而言,他这一行的颜色$[1,r_i+1]$是确定的,因为前$r_i$个是确定被染色,而$r_i+1$是必须不染色的.因此判断是否违法的条件就是看最后一列是否是强制被染色的即可,条件判断就是先找到那一列,然后对那一列来说,最后的一位是否覆盖到了第$i$行的范围,如果是的话就无解.对于列的情况也同理,对称处理即可.而统计答案的话,就遍历对$r_i+2$到边界的格子,看这一列上面往下伸是不是已经到了可以任意选择的位置,如果是,就累加.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+7,MOD = 1e9+7;
int r[N],c[N];
int qpow(int a,int b)
{
	int res = 1 % MOD;
	while(b)
	{
		if(b & 1)	res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
		b >>= 1;
	}
	return res;
}
int main()
{
	int h,w;scanf("%d%d",&h,&w);
	for(int i = 1;i <= h;++i)	scanf("%d",&r[i]);
    for(int i = 1;i <= w;++i)	scanf("%d",&c[i]);
    int ok = 1;
    for(int i = 1;i <= h;++i)
    	if(c[r[i] + 1] >= i)
    	{
    		ok = 0;
    		break;
    	}
    for(int i = 1;i <= w;++i)
    	if(r[c[i] + 1] >= i)
    	{
    		ok = 0;
    		break;
    	}
    if(!ok)	puts("0");
    else
    {
    	int res = 0;
    	for(int i = 1;i <= h;++i)
    	{
    		for(int j = r[i] + 2;j <= w;++j)
    		{
    			if(i >= c[j] + 2)	
    				++res;
    		}
    	}
    	printf("%d\n",qpow(2,res));
    }
    return 0;
}

C. Primes and Multiplication

题目大意:
定义$prime(x)$函数得到的是$x$的所有的质因数的集合.
定义$g(x,p)$函数的结果是最大的$p^k$且$p^k | x$.
定义$f(x,y)$函数的结果是所有的$p \in prime(x)$的$g(y,p)$的结果的乘积.

数据范围:
$2 \leq x \leq 10^9$
$1 \leq n \leq 10^{18}$

思路

这题数据范围大的离谱,从范围上入手,应该是一个$O(\sqrt{x})$的算法,大概的也就筛一下$x$里的所有的质因数.而且不能说遍历别的跟$n$有关的内容.
观察形式可以发现重复元素比较多,且和质因数$p$有关,考虑贡献:
假定现在在枚举的质因数是$p$,则每次都要枚举$p$的若干倍,记作$p^k$.对$g$函数而言,实际上就是在求$p$在里面一共有几次,出现了$k$次最后的结果就是$p^k$.则对于$p^k$对整个答案的影响,单个的$p^k$的贡献是$p$,而整个序列里一共要出现$\lfloor\frac{x}{p^k}\rfloor$次.原因是整个序列是相乘的形式,所以幂就是相加的形式,最终的答案幂次是整个序列里出现的次数.
分别统计即可.
注意会爆long long,套unsigned long long解决.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define int ll
vector<ll> p;
vector<vector<ll>> fact;
const int N = 2e6+7,MOD = 1e9+7;
int primes[N],cnt,st[N];
ll qpow(ll a,ll b)
{
	ll res = 1 % MOD;
	while(b)
	{
		if(b & 1)	res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
		b >>= 1;
	}
	return res;
}
void init()
{
	for(int i = 2;i < N;++i)
	{
		if(!st[i])	primes[cnt++] = i;
		for(int j = 0;primes[j] * i < N;++j)
		{
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0)	break;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	init();
	ll x,n;cin >> x >> n;
	for(int i = 0;i < cnt;++i)
	{
		if(x % primes[i] == 0)
		{
			p.push_back(primes[i]);
			while(x % primes[i] == 0)	x /= primes[i];
		}
	}
	if(x > 1)	p.push_back(x);
	ll res = 1;
	for(int i = 0;i < p.size();++i)
	{
		for(ll curp = p[i];curp <= n;curp *= p[i])
		{
			res = (res * qpow(p[i],n / curp)) % MOD;
			if(curp > n / p[i])	break;
		}
	}
	cout << res << endl;
    return 0;
}

D. Complete Tripartite

题目大意:给定一个$n$个点$m$条边的无向图.现要求把整个图上的点分成三类集合,每个集合没有交集,并且要使任意两个集合都是牛逼的.定义两个集合是牛逼的当且仅当两个集合没有交集且集合内部的所有点之间没有边相连,而两个集合之间的每个点都有边相连.要求构造一种方案,如果有多个输出一个即可.

数据范围:
$3 \leq n \leq 10^5$
$0 \leq m\leq \min(3*10^5,\frac{n*(n-1)}{2})$

思路

如果图不连通,则无解.
由于只要输出一种方案,不妨贪心的尝试构造.
首先对于一个点来说,如果他的集合已经确定了,那么与他直接相连的点必然来自于其他的集合.因此可以先钦定$1$点是分配到集合$1$的,那么对于与$1$直接相连的所有点来说他们就必然来自$2$或者$3$集合,而没有的就都属于$1$集合.在这些直接相连的点的集合中任意选出一个点,把他的颜色染成$2$并继续往外标记,那么遍历到的点如果满足是之前被$1$拓展到的点的话,就认为是属于$3$集合的,剩余的还没被标记的就一定是$2$集合的了.
考虑怎么判断是否合法,由于题目的条件特别强,就是说这个题目的条件他是使得对任意一个点来说,所有与它不属于一个集合的点都必须与它联通.从这个特别强的性质入手比较好.
记三种集合的点数分别为$c_1,c_2,c_3$显然三者之和的条件一定是满足的.
①考虑边数的条件,由于题目保证每两个点之间最多也就一个边相连,可以得到一个表达式:$c_1*(c_2+c_3) + c_2*c_3 = m$这是因为之前所说的,对于$1$集合里的节点来说,所有$2$集合的点和$3$节点的点必然与之相连,所以$1$与$2$点产生的边数就是$c_1*c_2$,其他同理,补上即可.
②对每个点来说与它相连接的点必然不能是同色的.
③对于每种颜色的节点来说,他的数量不能是$0$.
以上性质遍历验证即可.
本题有些细节问题比较细微,建议看代码的时候注意一下.最后还有一个实现上的问题:因为这张无向图是可能带有环的,所以普通的带有$fa$的$dfs$可能也还是跑的非常慢,甚至应该会死循环.对这种情况必须要加一个数组进行判断,这一点是不能省掉的.
最后还是提一下细节:
$1$号点是第一个点,他所在的集合是$1$.在遍历完与他相连的点之后,剩下的没有遍历到的点就是$1$的.钦定的点是与它相连的随便的一个点,它的所在的集合是$2$.与它相连的且与$1$相连的就是$3$.注意不要把已经有颜色的点给覆盖掉了.以及$1$号点的标记也是要打的,不打的话会误认为$1$不是已经在集合里的点.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7,M = 1e6+7;
int edge[M],succ[M],ver[N],idx;
int n,m,connected[N],col[N];
int st[N],ok = 1,fnlvis[N];

void add(int u,int v)
{
	edge[idx] = v;
	succ[idx] = ver[u];
	ver[u] = idx++;
}
void dfs(int u,int fa)
{
	connected[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(v == fa || connected[v])	continue;
		dfs(v,u);
	}
}
void dfs2(int u,int fa)
{
	fnlvis[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(v == fa || fnlvis[v])	continue;
		if(col[v] == col[u])	ok = 0;
		dfs2(v,u);
	}
}
int main()
{
	memset(ver,-1,sizeof ver);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;++i)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1,-1);
	for(int i = 1;i <= n;++i)
		if(!connected[i])
			return puts("-1"),0;
	col[1] = 1;st[1] = 1;
	for(int i = ver[1];~i;i = succ[i])
	{
		int v = edge[i];
		st[v] = 1;
	}	
	for(int i = 1;i <= n;++i)
		if(!st[i])	
			col[i] = 1;
	int v = edge[ver[1]];
	col[v] = 2;
	// cout << v << endl;
	for(int i = ver[v];~i;i = succ[i])
	{
		int u = edge[i];
		if(!col[u] && st[u])
			col[u] = 3;
	}
	// for(int i = 1;i <= n;++i)
		// cout << col[i] << " ";cout << endl;
	int cnt[4] = {0};
	for(int i = 1;i <= n;++i)
	{
		if(!col[i])	col[i] = 2;
		++cnt[col[i]];
	}
	// cout << cnt[1] << " " << cnt[2] << " " << cnt[3] << endl;
	if(!cnt[1] || !cnt[2] || !cnt[3])	return puts("-1"),0;
	if(cnt[1] * (cnt[2] + cnt[3]) + cnt[2] * cnt[3] != m)	return puts("-1"),0;
	for(int u = 1;u <= n;++u)
	{
		int c[4] = {0};
		for(int i = ver[u];~i;i = succ[i])
		{
			int v = edge[i];
			++c[col[v]];
		}
		if(c[col[u]] != 0)	return puts("-1"),0;
		if(col[u] == 1 && c[2] != cnt[2] && c[3] != cnt[3])	return puts("-1"),0;
		if(col[u] == 2 && c[1] != cnt[1] && c[3] != cnt[3])	return puts("-1"),0;
		if(col[u] == 3 && c[2] != cnt[2] && c[1] != cnt[1])	return puts("-1"),0;
	}
	for(int i = 1;i <= n;++i)
		printf("%d ",col[i]);
    return 0;
}